package 二叉树.二叉排序树;

class BinarySearchTree {
    private class Node {
        int data; // 数据域
        Node left; // 左子树
        Node right; // 右子树
    }
    /**
     * 创建二叉排序树
     * @param key
     */
    private Node root; // 二叉排序树根节点
    public void insert(int key) {
        Node p = new Node(); // 要插入的结点
        p.data = key;

        if(root == null) {
            root = p;
        } else {
            Node parent = new Node();
            Node current = root; // 当前结点
            while (true) {
                parent = current;
                if(key > current.data) {
                    current = current.right;
                    if (current == null) {
                        parent.right = p;
                        return;
                    }
                } else { // 这里不考虑key出现和二叉排序树结点中的值相等的情况
                    current = current.left;
                    if (current == null) {
                        parent.left = p;
                        return;
                    }
                }

            }
        }
    }
}


